package pri.hillchen.algorithm.desgin.leecode;

import java.util.HashMap;
import java.util.Map;

/**
 * Created by hillchen on 2017/9/29 0029.
 */
public class LRUCache {
    class CacheEle{
        private int key;
        private int value;
        private CacheEle before, after;
        CacheEle(int key,int value){
            this.key = key;
            this.value = value;
        }
    }

    private CacheEle head,tail;
    private int capacity,size;
    private Map<Integer,CacheEle> eleMaps;

    public LRUCache(int capacity) {
        if(capacity <= 0){
            throw new RuntimeException("cache capacity not be <= 0 !");
        }
        this.eleMaps = new HashMap<Integer,CacheEle>(capacity);
        this.capacity = capacity;
        this.size = 0;
    }

    private void visitEle(CacheEle visitEle){
        if(visitEle != head){
            if(visitEle == this.tail){
                visitEle.after = this.head;
                this.head.before = visitEle;
                CacheEle newTail = this.tail.before;
                newTail.after = null;

                this.head = visitEle;
                this.tail = newTail;

            }else{
                CacheEle beferEle = visitEle.before;
                CacheEle afterEle = visitEle.after;

                beferEle.after = afterEle;
                afterEle.before = beferEle;
                visitEle.after = this.head;
                this.head.before = visitEle;
                this.head = visitEle;
            }
        }
    }

    public int get(int key) {
        //如果cache中是否存在key
        if(eleMaps.containsKey(key)){
            CacheEle keyEle = this.eleMaps.get(key);
            visitEle(keyEle);
            return this.head.value;

        }else{
            return -1;
        }
    }

    public void put(int key, int value) {
        CacheEle newEle = new CacheEle(key,value);
        //添加第一个元素时
        if(this.head == null && this.tail == null){
            head = newEle;
            tail = newEle;
            size ++;

            this.eleMaps.put(key,newEle);
        }else{//当不是添加第一个元素时,先判断是否存在该缓存，如果存在则将原来的元素去掉然后在添加该元素
            if(this.eleMaps.containsKey(key)){
                CacheEle oldEle = this.eleMaps.get(key);
                visitEle(oldEle);
                this.head.value = value;
            }else{
                //当添加元素后超过容量时
                if(this.size == this.capacity){
                    newEle.after = this.head;
                    this.head.before = newEle;
                    this.eleMaps.remove(this.tail.key);
                    CacheEle newTail = this.tail.before;
                    newTail.after = null;

                    this.head = newEle;
                    this.tail = newTail;
                }else{//当添加元素后没有超过容量时
                    newEle.after = this.head;
                    this.head.before = newEle;
                    this.head = newEle;
                    size ++;
                }
                this.eleMaps.put(key,newEle);
            }
        }
    }

    public static void main(String[] args){

        LRUCache cache = new LRUCache(2);
        cache.put(1,1);
        cache.put(2,2);
        System.out.println(cache.get(1));       // returns 1
        cache.put(3, 3);    // evicts key 2
        System.out.println(cache.get(2));       // returns -1 (not found)
        cache.put(4, 4);    // evicts key 1
        System.out.println(cache.get(1));       // returns -1 (not found)
        System.out.println(cache.get(3));        // returns 3
        System.out.println(cache.get(4));
    }
}

